#ifndef __BP__HEADER__
#define __BP__HEADER__
#include "b+.h"
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int getRecordSize(int keyNumber,KeyStruct keyArray[],int indexSize){
    int size = 0;
    for(int i = 0;i < keyNumber;i ++){
        switch(keyArray[i].flag){
            case KEY_INT:            
                size += 4;
                break;
            case KEY_DOUBLE:
                size += 8;
                break;
            case KEY_CHAR:
                size += keyArray[i].strlength;
                break;
        }
    }
    return size + indexSize;
}

int getFileHeaderLength(int keyNumber){
    return sizeof(struct key) * keyNumber + sizeof(struct FileHeader);
}

void freeBPNodeStructPoint(BPNodeStructPoint m_bpNode){
    
    BlockHeaderLinkPoint tmp,now = m_bpNode->m_blockHeaderLink;
    while(now != NULL){
        tmp = now->next;
        free(now->m_blockHeader);
        free(now);
        now = tmp;
    }
    free(m_bpNode->m_dataP);
    free(m_bpNode);
}


void freeAndWriteBackBPNodeStructPoint(FILE * fp,
FileHeaderStructPoint fhsp,
BPNodeStructPoint m_bpNode){
    writeBackBPNode(fp,fhsp,m_bpNode);
    freeBPNodeStructPoint(m_bpNode);
}

// Reserve memcpy.
void * rmemcpy(void * dst,void * rst,int n){
    for(int i = n - 1;i >= 0;i--){
        *((char *)dst + i) = *((char *)rst + i);  
    }
}

void initBPFile(FILE * fp,int keyNumber,KeyStruct keyArray[]){
    fseek(fp,0,SEEK_SET);

    FileHeaderStruct fileHeaderStruct;
    fileHeaderStruct.headerLength = getFileHeaderLength(keyNumber);
    fileHeaderStruct.m = 1024;
    
    // Only int type can become index type.
    fileHeaderStruct.recordSize = getRecordSize(keyNumber,keyArray,4);
    fileHeaderStruct.blockSize = 16;
    fileHeaderStruct.indexSize  = 4;

    fileHeaderStruct.startBlock = 0;
    fileHeaderStruct.firstAvailableBlock = 0;
    fileHeaderStruct.lastAvailableBlock = 0;
    fileHeaderStruct.startDataBlock = 0;
    fileHeaderStruct.endDataBlock = 0;

    fileHeaderStruct.keyNumber = keyNumber;
    fileHeaderStruct.allockedBlockNumber = 0;
    fseek(fp,0,SEEK_SET);
    fwrite(&fileHeaderStruct,sizeof(FileHeaderStruct),1,fp);
    for(int i = 0;i < keyNumber;i++){
        fwrite(&(keyArray[i]),sizeof(KeyStruct),1,fp);
    }
    return;
}

// search or create
BPNodeStructPoint segetNodeByIndex(FILE * fp,FileHeaderStructPoint fhsp,int index,BPNodeStructPoint bpNode){
    int * data = bpNode->m_dataP;
    int i;
    for(i = 0;i < bpNode->number;i++){
        if(*(data + 1 + i *2) >= index){
            break;
        }
    }

    if(bpNode->number == 0){
        BPNodeStructPoint nextNode = getAFreeBPNode(fp,fhsp,1);
        nextNode->m_blockHeaderLink->m_blockHeader->parentNode = bpNode->m_blockHeaderLink->m_blockHeader->pos;

    
    }

    BPNodeStructPoint nextNode = getBPNodeByNumber(fp,fhsp,bpNode->number);
    freeBPNodeStructPoint(bpNode);

    if(nextNode->type == INDEX_NODE){
        return searchNodeByIndex(fp,fhsp,index,nextNode);
    }else{
        return nextNode;
    }
} 

BPNodeStructPoint searchNodeByIndex(FILE * fp,FileHeaderStructPoint fhsp,int index,BPNodeStructPoint bpNode){
    int * data = bpNode->m_dataP;
    int i;
    for(i = 0;i < bpNode->number;i++){
        if(*(data + 1 + i *2) >= index){
            break;
        }
    }

    if(bpNode->number == 0){
        return NULL;
    }

    BPNodeStructPoint nextNode = getBPNodeByNumber(fp,fhsp,bpNode->number);
    freeBPNodeStructPoint(bpNode);

    if(nextNode->type == INDEX_NODE){
        return searchNodeByIndex(fp,fhsp,index,nextNode);
    }else{
        return nextNode;
    }

}

// void borrowLeftNodeData(
//     FILE * fp,
//     FileHeaderStructPoint fhsp,
//     BPNodeStructPoint bpNode,
//     BPNodeStructPoint leftNode
// ){
    
// }

// void borrowRightNodeData(
//     FILE * fp,
//     FileHeaderStructPoint fhsp,
//     BPNodeStructPoint bpNode,
//     BPNodeStructPoint leftNode
// ){

// }


// void mergeLeftNode(
//     FILE * fp,
//     FileHeaderStructPoint fhsp,
//     BPNodeStructPoint bpNode
// ){

// }

// void mergeRightNode(
//     FILE * fp,
//     FileHeaderStructPoint fhsp,
//     BPNodeStructPoint bpNode
// ){

// }

// void delSmallNode(
//     FILE * fp,
//     FileHeaderStructPoint fhsp,
//     BPNodeStructPoint bpNode
// ){
//     if(bpNode->type == INDEX_NODE){
//         BlockHeaderStructPoint bhsp = bpNode->m_blockHeaderLink->m_blockHeader;
        
//         if(bhsp->nodePrefix == 0){
//             BPNodeStructPoint prefixNode = getBPNodeByNumber(fp,fhsp,bhsp->nodeNext);
//             if(prefixNode->number > (fhsp->m +1)/2 -1){
//                 borrowRightNodeData(fp,fhsp,bpNode);            
//             }else{
//                 mergeLeftNode(fp,fhsp,bpNode);
//             }
//         }else{  
//             BPNodeStructPoint prefixNode = getBPNodeByNumber(fp,fhsp,bhsp->nodePrefix);
//             if(prefixNode->number > (fhsp->m +1)/2 -1){
//                 borrowLeftNodeData(fp,fhsp,bpNode);            
//             }else{
//                 mergeRightNode(fp,fhsp,bpNode);
//             }
            
//         }

        

//     }else{

//     }

// }

// if number > M/2;
// if number <= M/2;
// Don't change the index node unless 
// influence the index node 
// when merging the data node or borrowing the brother data node. 
bool deleteDataByIndex(
    FILE * fp,
    FileHeaderStructPoint fhsp,
    BPNodeStructPoint bpNode,
    int index){
    char * data = bpNode->m_dataP;
    int number = bpNode->number;
    int i;
    
    for(i = 0;i < number;i++){
        if(* (int *) (data + (fhsp->recordSize) * i) == index){
            break;
        }
    }

    if(i == number){
        return false;
    }else{
        memcpy(data + (fhsp->recordSize) * i,data + (fhsp->recordSize) *(i+1), (number - (i+1)) * (fhsp->recordSize));
        bpNode->number -= 1;
        
        // 当数量小于m/2节点不合并了
        // if(bpNode->number < (fhsp->m+1)/2){
        //     if(bpNode->m_blockHeaderLink->m_blockHeader->parentNode != 0){
        //         delSmallNode(fp,fhsp,bpNode);
        //     }
        // }

        writeBackBPNode(fp,fhsp,bpNode);
        return true;
    }

}

BPNodeStructPoint newBPNode(FILE * fp,FileHeaderStructPoint fhsp){
    int blockSize = fhsp->blockSize * 1024;
    int blockDataSize = blockSize - sizeof(BlockHeaderStruct);
    BPNodeStructPoint bpNode = (BPNodeStructPoint)malloc(sizeof(BPNodeStruct));
    bpNode->m_blockHeaderLink = malloc(sizeof(BlockHeaderStruct));
    bpNode->m_blockHeaderLink->m_blockHeader = malloc(sizeof(BlockHeaderStruct));
    bpNode->m_blockHeaderLink->m_blockHeader->pos = fhsp->allockedBlockNumber + 1;
    bpNode->m_dataP = malloc(blockDataSize);

    fseek(fp,0,SEEK_END);
    
    fwrite(bpNode->m_blockHeaderLink->m_blockHeader,sizeof(BlockHeaderStruct),1,fp);
    fwrite(bpNode->m_dataP,blockDataSize,1,fp);

    fhsp->allockedBlockNumber += 1;
    writeBackFileHeader(fp,fhsp);

    return bpNode;
}

BPNodeStructPoint getOneFreeBPBlock(FILE * fp,FileHeaderStructPoint fhsp){
    // GetFreeNode from already alloc node.
    printf("debug:%d",fhsp->firstAvailableBlock );
    fflush(stdout);
    if(fhsp->firstAvailableBlock != 0){
        BPNodeStructPoint m_bpNode = getBPNodeByNumber(fp,fhsp,fhsp->firstAvailableBlock);
        BlockHeaderStructPoint bhsp = m_bpNode->m_blockHeaderLink->m_blockHeader;

        bhsp->number = 0;

        fhsp->firstAvailableBlock = m_bpNode->m_blockHeaderLink->m_blockHeader->blockNext;
        writeBackFileHeader(fp,fhsp);
        return m_bpNode;
    }else{ // GetFreeNode by allocing new node.
        return newBPNode(fp,fhsp);
    }
}

BPNodeStructPoint getAFreeBPNode(FILE * fp,FileHeaderStructPoint fhsp,int blockNumber){
   
    BPNodeStructPoint bpNode = getOneFreeBPBlock(fp,fhsp);
    printf("**%d**",1);
    if(blockNumber == 1){
        bpNode->m_blockHeaderLink->m_blockHeader->blockNumber = 1;
        return bpNode;
    }
    
    BPNodeStructPoint tmp = NULL;

    free(bpNode->m_dataP);

    int blockSize = fhsp->blockSize;
    int blockDataSize = blockSize - sizeof(BlockHeaderStruct);
    BlockHeaderLinkPoint bhlp = bpNode->m_blockHeaderLink;

    bpNode->m_dataP = malloc(sizeof(blockDataSize));

    for(int i = 1;i < blockNumber;i++){
        tmp = getOneFreeBPBlock(fp,fhsp);
        bhlp->next = tmp->m_blockHeaderLink;
        free(tmp->m_dataP);
        free(tmp);
    }

    bhlp->next = NULL;
    bpNode->m_blockHeaderLink->m_blockHeader->blockNumber = blockNumber;
    return bpNode;
    
}

bool expendBPNodeSize(FILE * fp,FileHeaderStructPoint fhsp,BPNodeStructPoint bpNode){
    BPNodeStructPoint newBPBlock = getAFreeBPNode(fp,fhsp,1);
    bpNode->number += 1;
    bpNode->m_dataP = realloc(bpNode->m_dataP,bpNode->number * (fhsp->blockSize - sizeof(BlockHeaderStruct)));
    BlockHeaderLinkPoint tmp = bpNode->m_blockHeaderLink;
    while(tmp->next != NULL){
        tmp = tmp->next;
    }
    tmp->next = newBPBlock->m_blockHeaderLink;
    tmp->m_blockHeader->blockNext = tmp->next->m_blockHeader->pos;
    free(bpNode->m_dataP);
    free(bpNode);
    return true;
}

// Only in the insert progress,the B+ tree can be divised.
// The division is a recursion progress.
// In the recursion progress we need insert data.
int diviseBPNode(
    FILE * fp,
    FileHeaderStructPoint fhsp,
    BPNodeStructPoint bpNode,
    int index
    )
{
    
    if(bpNode->type == INDEX_NODE){
        int halfMCeil = fhsp->m /2;
        int offset = (halfMCeil + 1) * (fhsp->indexSize + 4);
        int leftSize = (fhsp->m - 1 - halfMCeil) * (fhsp->indexSize + 4) + 4; 
        bpNode->number = halfMCeil;

        int midIndex =* (int *) ((char *)(bpNode->m_dataP) + (halfMCeil * (fhsp->indexSize + 4)) + 4);

        bpNode->m_blockHeaderLink->m_blockHeader->nodeNext = 0; // ?
        
        int rightNodeBlockNumber = leftSize % fhsp->blockSize == 0 ? (leftSize / fhsp->blockSize) : (leftSize / fhsp->blockSize) +1;


        BPNodeStructPoint rightNode =  getAFreeBPNode(fp,fhsp,rightNodeBlockNumber);

        rightNode->number = fhsp->m - halfMCeil - 1;



        memcpy(rightNode->m_dataP,((char *)(bpNode->m_dataP) + ((halfMCeil + 1)* (fhsp->indexSize + 4))) ,leftSize);

        BlockHeaderStructPoint lbhsp = bpNode->m_blockHeaderLink->m_blockHeader;
        BlockHeaderStructPoint rbhsp = rightNode->m_blockHeaderLink->m_blockHeader;
        
        //Although standard B+ don't need pre index or next index in index node,
        //we need this information which will use in delete progress.

        rbhsp->nodeNext = lbhsp->nodeNext;
        lbhsp->nodeNext = rbhsp->pos;
        rbhsp->nodePrefix = lbhsp->pos;

        int rightStartIndex = * (int *)(rightNode->m_dataP);

        int pos;
        if(rightStartIndex >= index){
            pos = rbhsp -> pos; 
        }else{
            pos = lbhsp-> pos;
        }

        void * indexdata = malloc(sizeof(int) * 3);

        * (int *)indexdata = lbhsp->pos;
        * (int *)(indexdata + 1) = midIndex;
        * (int *)(indexdata + 2) = rbhsp->pos; 
        BPNodeStructPoint parent = getBPNodeByNumber(fp,fhsp,lbhsp->parentNode);

        int parentNodeIndex = insertToIndexNode(fp,fhsp,midIndex,indexdata,parent);

        rbhsp->parentNode = parentNodeIndex;
        lbhsp->parentNode = parentNodeIndex;

        writeBackBPNode(fp,fhsp,bpNode);
        writeBackBPNode(fp,fhsp,bpNode);

        if(rbhsp->nodeNext == 0){
            fhsp->endDataBlock = rbhsp->pos;
            writeBackFileHeader(fp,fhsp);
        }

        return pos;
    }else{
        int halfMCeil = (fhsp->m+1 + 1)/2;
        bpNode->number = halfMCeil;

        int offset = halfMCeil * (fhsp->recordSize);
        int leftSize =  (fhsp->recordSize) * (fhsp->m + 1 - halfMCeil);
    
        int midIndex =* (int *) ((char *)(bpNode->m_dataP) + offset);

        
        int rightNodeBlockNumber = leftSize % fhsp->blockSize == 0 ? (leftSize / fhsp->blockSize) : (leftSize / fhsp->blockSize) +1;


        BPNodeStructPoint rightNode =  getAFreeBPNode(fp,fhsp,rightNodeBlockNumber);
        rightNode->number = fhsp->m + 1 - halfMCeil;


        memcpy(rightNode->m_dataP,((char *)(bpNode->m_dataP) + ((halfMCeil + 1)* (fhsp->indexSize + 4))) ,leftSize);

        BlockHeaderStructPoint lbhsp = bpNode->m_blockHeaderLink->m_blockHeader;
        BlockHeaderStructPoint rbhsp = rightNode->m_blockHeaderLink->m_blockHeader;
        
        rbhsp->nodeNext = lbhsp->nodeNext;
        lbhsp->nodeNext = rbhsp->pos;
        rbhsp->nodePrefix = lbhsp->pos;

        int rightStartIndex = * (int *)(rightNode->m_dataP);

        int pos;
        if(rightStartIndex >= index){
            pos = rbhsp -> pos; 
        }else{
            pos = lbhsp-> pos;
        }

        void * indexdata = malloc(sizeof(int) * 3);

        * (int *)indexdata = lbhsp->pos;
        * (int *)(indexdata + 1) = midIndex;
        * (int *)(indexdata + 2) = rbhsp->pos; 
        BPNodeStructPoint parent = getBPNodeByNumber(fp,fhsp,lbhsp->parentNode);

        int parentNodeIndex = insertToIndexNode(fp,fhsp,midIndex,indexdata,parent);

        rbhsp->parentNode = parentNodeIndex;
        lbhsp->parentNode = parentNodeIndex;

        writeBackBPNode(fp,fhsp,bpNode);
        writeBackBPNode(fp,fhsp,bpNode);

        return pos;

    }
}


int insertToIndexNode(
    FILE * fp,
    FileHeaderStructPoint fhsp,
    int index,
    void * data,
    BPNodeStructPoint bpNode
){
    int number = bpNode -> number;
    int capsity = bpNode->m_blockHeaderLink->m_blockHeader->blockNumber 
    * (fhsp->blockSize * 1024 - sizeof(BlockHeaderStruct));
    capsity = ( capsity - 4) / 8;

    if(number == capsity){
        expendBPNodeSize(fp,fhsp,bpNode);
    }

    if(number == 0){
        memcpy(bpNode->m_dataP,data,12);
        bpNode->number += 1;
        return bpNode->m_blockHeaderLink->m_blockHeader->pos;
    }

    int i;
    int itemSize = 8; // ?
    char * cdata = (char *)bpNode->m_dataP;

    for(i = 0;i < number;i++){
        if( * (int *)(cdata + itemSize * i + 4) >= index){
            break;
        }
    }
    
    rmemcpy((char *)cdata + (i*itemSize) + 8,(char *)cdata + (i*itemSize),(number - i) * 8);
    bpNode->number += 1;

    if(bpNode->number == fhsp->m){
        return diviseBPNode(fp,fhsp,bpNode,index);
    }

}

// return -1 represent the primary key crash.

int insertToDataNode(
    FILE * fp,
    FileHeaderStructPoint fhsp,
    int index,
    void * data,
    BPNodeStructPoint bpNode
){

    int number = bpNode -> number;
    int capsity = bpNode->m_blockHeaderLink->m_blockHeader->blockNumber 
    * (fhsp->blockSize * 1024 - sizeof(BlockHeaderStruct));

    capsity = capsity / (fhsp->recordSize);

    if(number == capsity){
        expendBPNodeSize(fp,fhsp,bpNode);
    }

    if(number == 0){
        memcpy(bpNode->m_dataP,data,12);
        bpNode->number += 1;
        return bpNode->m_blockHeaderLink->m_blockHeader->pos;
    }

    int i;
    int itemSize = fhsp->recordSize; // ?
    char * cdata = bpNode->m_dataP;

    for(i = 0;i < number;i++){
        int tmp = * (int *)(cdata + itemSize * i) ;
        if( tmp == index){
            return -1;
        }else if(tmp > index){
            break;
        }
    }
    
    rmemcpy((char *)cdata + ((i + 1)*itemSize) ,(char *)cdata + (i*itemSize),(number - i) * itemSize);
    bpNode->number += 1;

    if(bpNode->number > fhsp->m ){
        return diviseBPNode(fp,fhsp,bpNode,index);
    }else{
        return bpNode->m_blockHeaderLink->m_blockHeader->pos;
    }

}

int insertData(FILE * fp,int index,void * data,bool isAutoIncrement){
    FileHeaderStruct fhs;
    fseek(fp,0,SEEK_SET);
    fread(&fhs,sizeof(FileHeaderStruct),1,fp);
    
    int a[1000];
    printBPtree(fp,&fhs,a,0,0,1000);

    BPNodeStructPoint bpNode = NULL;


    // 插入到B+树的最后一个
    if(isAutoIncrement){
        if(fhs.endDataBlock == 0){
            bpNode = newBPNode(fp,&fhs);
            BlockHeaderStructPoint bhsp = bpNode->m_blockHeaderLink->m_blockHeader;
            fhs.startBlock = bhsp->pos;
            fhs.endDataBlock = fhs.startBlock;
        }else{
            bpNode = getBPNodeByNumber(fp,&fhs,fhs.endDataBlock);
        }

        int number = bpNode->number;

        char * cdata = (char *)(bpNode->m_dataP);
        
        cdata += (number - 1) * fhs.recordSize;


        cdata += fhs.recordSize;
        int newIndex = * (int *) cdata + 1;

        * (int *)cdata = newIndex;

        cdata += 4;
        memcpy(cdata,data,fhs.recordSize - fhs.indexSize);
        
        bpNode->number += 1;
        fhs.endDataBlock = bpNode->m_blockHeaderLink->m_blockHeader->pos;
        if(bpNode->number > fhs.m){
            int endDataBlock = diviseBPNode(fp,&fhs,bpNode,newIndex);
            fhs.endDataBlock  = endDataBlock;    
        }

        writeBackFileHeader(fp,&fhs);  

        return newIndex;

    }else{
        printf("hel\n");
        fflush(stdout);

        BPNodeStructPoint bpNode = getBPNodeByNumber(fp,&fhs,fhs.startBlock);
        
        // 说明该数据节点就是头结点
        if(bpNode->m_blockHeaderLink->m_blockHeader->pos = fhs.startBlock){
            bpNode->type = DATA_NODE;
            bpNode->m_blockHeaderLink->m_blockHeader->nodePrefix = 0;
            bpNode->m_blockHeaderLink->m_blockHeader->nodeNext = 0;
            bpNode->m_blockHeaderLink->m_blockHeader->type = DATA_NODE;
            fhs.startBlock = bpNode->m_blockHeaderLink->m_blockHeader->pos;
            fhs.endDataBlock = bpNode->m_blockHeaderLink->m_blockHeader->pos;
            fhs.startDataBlock = bpNode->m_blockHeaderLink->m_blockHeader->pos;
            writeBackFileHeader(fp,&fhs);
        }
        
        printBPtree(fp,&fhs,a,0,0,1000);
        printf("\nkali600\n");
        fflush(stdout);
        
        if(bpNode->type == DATA_NODE){
            insertToDataNode(fp,&fhs,index,data,bpNode);
        }else{
            BPNodeStructPoint dataNode = segetNodeByIndex(fp,&fhs,index,bpNode);
            insertToDataNode(fp,&fhs,index,data,dataNode);
        }
    }


}   


void writeBackFileHeader(FILE * fp,FileHeaderStructPoint fhsp){
    fseek(fp,0,SEEK_SET);
    fwrite(fhsp,sizeof(FileHeaderStruct),1,fp);
}

// 策略一 默认采用策略一
// 每次写回时判断物理块是否存在内容，多余的物理块放在availableBlock中，
// 即将最后一个node block的blockNext置0
// 并将lastAvailableBlock着哦功能
//

// 策略二
// 节点内块只会分配，不会回收
// 只有当节点删除时，块才会回收
// 可以防止物理块的频繁分配？

void writeBackBPNode(FILE * fp,FileHeaderStructPoint fhsp,BPNodeStructPoint bpNode){
    int blockSize = fhsp->blockSize * 1024;
    int blockDataSize = blockSize - sizeof(BlockHeaderStruct);

// 策略一：


 int needSize;
    switch (bpNode->type)
    {
        case 1:
            needSize = fhsp->indexSize * bpNode->number;
            break;
        case 3:
            needSize = fhsp->recordSize * bpNode->number;
            break;
        default:
            freeBPNodeStructPoint(bpNode);
            printf("\nerror: B+ file is destroyed!\n");
    }

    char * idx = bpNode->m_dataP;
    BlockHeaderLinkPoint tmp = bpNode->m_blockHeaderLink;

    int blockNumer = needSize % blockDataSize == 0 ? (needSize / blockDataSize) :  (needSize / blockDataSize) + 1;
    bool shouldRecycle = true;

    if(blockNumer == tmp->m_blockHeader->blockNumber){
        shouldRecycle = false;
    }else{
        tmp->m_blockHeader->blockNumber = blockNumer;
    }
    
    tmp->m_blockHeader->number = bpNode->number;

    fseek(fp,fhsp->headerLength + blockSize * (tmp->m_blockHeader->pos - 1),SEEK_SET);
    fwrite(tmp->m_blockHeader,sizeof(struct BlockHeader),1,fp);
    fwrite(idx,blockDataSize,1,fp);


    for(int alreadyWriteSize = blockDataSize;alreadyWriteSize < needSize;alreadyWriteSize += blockDataSize){
        tmp = tmp->next;
        idx += blockDataSize;
        
        fseek(fp,fhsp->headerLength + blockSize * (tmp->m_blockHeader->pos - 1),SEEK_SET);

        fwrite(tmp->m_blockHeader,sizeof(struct BlockHeader),1,fp);
        fwrite(idx,blockDataSize,1,fp);
    }

    if(shouldRecycle){
        // 需要把最后一个块的下一块地址取0
        tmp->m_blockHeader->blockNext = 0;
        fseek(fp,fhsp->headerLength + blockSize * (tmp->m_blockHeader->pos - 1),SEEK_SET);
        fwrite(tmp->m_blockHeader,sizeof(struct BlockHeader),1,fp);

        // 回收物理快只用将lastAvailableBlock指向的block的blockNext修改为回收空闲块的首块地址
        // 然后将lastAvailableBlock修改为free block的最后一块

        tmp = tmp->next;
        int pos = tmp->m_blockHeader->pos;

        fseek(fp,fhsp->headerLength + blockSize * (fhsp->lastAvailableBlock - 1),SEEK_SET);
        
        BlockHeaderStruct blockheader;
        
        fread(&blockheader,sizeof(struct BlockHeader),1,fp);
        blockheader.blockNext = pos;

        fseek(fp,fhsp->headerLength + blockSize * (fhsp->lastAvailableBlock - 1),SEEK_SET);
        fwrite(&blockheader,sizeof(struct BlockHeader),1,fp);


        while(tmp->next != NULL){
            tmp = tmp->next;
        }

        pos = tmp->m_blockHeader->pos;
        fhsp->lastAvailableBlock = pos;

        writeBackFileHeader(fp,fhsp);
    }

/* 策略二：

    int needSize;
    switch (bpNode->type)
    {
        case 1:
            needSize = fhsp->indexSize * bpNode->number;
            break;
        case 3:
            needSize = fhsp->recordSize * bpNode->number;
            break;
        default:
            freeBPNodeStructPoint(bpNode);
            printf("\nerror: B+ file is destroyed!\n");
    }

    char * idx = bpNode->m_dataP;
    BlockHeaderLinkPoint tmp = bpNode->m_blockHeaderLink;

    // 修改数目
    tmp->m_blockHeader->number = bpNode->number;

    while(tmp != NULL){
        fseek(fp,fhsp->headerLength + blockSize * (tmp->m_blockHeader->pos - 1),SEEK_SET);
        fwrite(tmp->m_blockHeader,sizeof(struct BlockHeader),1,fp);
        fwrite(idx,blockDataSize,1,fp);
        tmp = tmp->next;
        idx += blockDataSize;
    }
*/
}



void printBPtree(FILE * fp,FileHeaderStructPoint fhsp,int * stack,int start,int end,int size){
    
    //printf("file header:\n");
    printf("blockSize:\t\t %d\n",fhsp->blockSize);
    printf("headerLength:\t\t %d\n",fhsp->headerLength);
    printf("keyNumber:\t\t %d\n",fhsp->keyNumber);
    printf("m:\t\t\t %d\n",fhsp->m);
    printf("indexSize:\t\t %d\n",fhsp->indexSize);
    printf("recordSize:\t\t %d\n",fhsp->recordSize);
    printf("startBlock:\t\t %d\n",fhsp->startBlock);
    printf("firstAvailableBlock:\t %d\n",fhsp->firstAvailableBlock);
    printf("lastAvailableBlock:\t %d\n",fhsp->lastAvailableBlock);
    printf("startDataBlock:\t\t %d\n",fhsp->startDataBlock);
    printf("endDataBlock:\t\t %d\n",fhsp->endDataBlock);
    printf("allockedBlockNumber:\t %d\n",fhsp->allockedBlockNumber);
    
    while(start != end){
        if(start == size){
            start = 0;
        }
        BPNodeStructPoint bpNode =  getBPNodeByNumber(fp,fhsp,*(stack+start));
        start ++;

        if(bpNode->type == INDEX_NODE){
            int * data = bpNode->m_dataP;
            printf("%d index node pos:\t",bpNode->m_blockHeaderLink->m_blockHeader->pos);
            printf("%d",* data);
            *(stack+ end) = * data;
            end ++;
            if(end == size){
                end == 0;
            }
            for(int i = 0;i < bpNode->number;i++){
                printf("-|%d|-%d",*(data+i*2+1),*(data+i*2+2));
                *(stack+ end) = * (data+i*2+2);
                end ++;
                if(end == size){
                    end == 0;
                }
            }
            printf("\n");
            
        }else{
            printf("%d data node pos:\t",bpNode->m_blockHeaderLink->m_blockHeader->pos);
            char * data = bpNode->m_dataP;
            for(int i = 0;i < bpNode->number;i++){
                printf("%d ", * (int *) (data + i * fhsp->recordSize));
            }
            printf("\n");
        }
        freeBPNodeStructPoint(bpNode);
    }
    fflush(stdout);
}


BPNodeStructPoint getBPNodeByNumber(FILE * fp,FileHeaderStructPoint fhsp,int number){
   
    if(number == 0){
        BPNodeStructPoint bpNode = getAFreeBPNode(fp,fhsp,1);
        fhsp->startBlock = bpNode->m_blockHeaderLink->m_blockHeader->pos;
        writeBackFileHeader(fp,fhsp);
        return bpNode;
    }

    int blockSize = fhsp->blockSize * 1024;
    int blockDataSize = blockSize - sizeof(BlockHeaderStruct);
    
    BPNodeStructPoint bpNode = (BPNodeStructPoint)malloc(sizeof(BPNodeStruct));
    fseek(fp,fhsp->headerLength + blockSize * (number - 1),SEEK_SET);

    BlockHeaderStructPoint nodeHeader = (BlockHeaderStructPoint)malloc(sizeof(BlockHeaderStruct));
    fread(nodeHeader,sizeof(BlockHeaderStruct),1,fp);
    
    bpNode->type = nodeHeader->type;
    bpNode->number = nodeHeader->number;
    bpNode->m_blockHeaderLink = malloc(sizeof(BlockHeaderLinkPoint));
    bpNode->m_blockHeaderLink->m_blockHeader = nodeHeader;
    bpNode->m_blockHeaderLink->next = NULL;

    void * data = NULL;
    int blockNumber = nodeHeader->blockNumber;
    if(blockNumber == 1){
        data = malloc(blockDataSize);
        fread(data,blockDataSize,1,fp);
        bpNode->m_dataP =  data;
    }else{
        data = malloc(blockDataSize * blockNumber);
        BlockHeaderLinkPoint tmp =  bpNode->m_blockHeaderLink;
        fread(data,blockDataSize,1,fp);
        bpNode->m_dataP =  data;
        int blockIndex = nodeHeader->nodeNext;

        char * now = data;
        now += blockDataSize;
        BlockHeaderStructPoint blockHeader;

        for(int i = 1;i < blockNumber;i++){
            if(blockIndex < 1){
                free(bpNode);
                return NULL;
            }  

            fseek(fp,blockSize * (blockIndex - 1) + fhsp->headerLength,SEEK_SET);
            BlockHeaderStructPoint blockHeader = (BlockHeaderStructPoint)malloc(sizeof(BlockHeaderStruct));

            fread(blockHeader,sizeof(BlockHeaderStruct),1,fp);
            tmp->next = (BlockHeaderLinkPoint)malloc(sizeof(BlockHeaderLinkPoint));
            tmp = tmp->next;
            tmp->next = NULL;
            tmp->m_blockHeader = blockHeader;

            blockIndex = blockHeader->blockNext;
            fread(now,blockDataSize,1,fp);
            now += blockDataSize;

        }
        
    }   

    return bpNode;
}